#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

string checkPalindrom(string &str, int l, int r)
{
    string rtn;
    while (l >= 0 && r <= str.size()) {
        if (str[l] == str[r]) {l--; r++;}    
        else break;
    }
    rtn = str.substr(l+1, r-l-1);
    return rtn;
}

//method 1  pass in the online judge
class Solution1 {
    public:
        string longestPalindrome(string s) {
            string best = s.substr(0,1);;
            for (int i = 0; i < s.size(); i++) {
                //cout << best << endl;
                string result;
                result = checkPalindrom(s, i, i);
                if (result.size() > best.size())
                    best = result;
                
                result = checkPalindrom(s, i, i+1); 
                if (result.size() > best.size())
                    best = result;
            }
            return best;
        }
};

int main(int argc, char **argv)
{
    Solution mySolution;
    string result;
    string input;
    input = "abacdfgdcaba";
    //input = "cnbabbakh";
    input = "cc";
    result = mySolution.longestPalindrome(input);
    cout << "Result is " << result << endl;
}
